package com.gitee.feizns.explore.data_structure.tree.bs.mid;

/**
 * @author feizns
 * @since 2020/3/10
 */
public class DeleteNode {

    public static void main(String[] args) {

    }

    public static TreeNode deleteNode(TreeNode root, int key) {
        if ( root != null ) {
            if ( key < root.val )
                root.left = deleteNode(root.left, key);
            else if ( key > root.val )
                root.right = deleteNode(root.right, key);
            else {
                if ( root.left == null && root.right == null )
                    return null;
                else if ( root.left == null )
                    return root.right;
                else if ( root.right == null )
                    return root.left;
                else {
                    TreeNode min = min(root.right);
                    root.val = min.val;
                    root.right = deleteNode(root.right, min.val);
                }
            }
        }
        return root;
    }

    private static TreeNode min(TreeNode node) {
        return node.left != null ? min(node.left) : node;
    }

}
